package OptimalAlgorithm.DivideAndConquer_Quicksort;

import java.util.Random;

//https://leetcode.cn/problems/sort-an-array/description/
public class SortArray {
    public int[] sortArray(int[] nums) {
        qsort(nums,0, nums.length - 1);
        return nums;
    }
    public void qsort(int[] nums,int l,int r){
        if(r <= l){
            return;
        }
        Random random = new Random();
        int left = l - 1;
        int right = r + 1;
        int key = nums[random.nextInt(nums.length) % (r - l + 1) + l];
        int i = l;
        while (i <= right - 1){
            if(nums[i] == key){
                i++;
            }else if(nums[i] < key){
                swap(left + 1,i,nums);
                i++;
                left++;
            }else {
                swap(right - 1,i,nums);
                right--;
            }
        }
        qsort(nums,l,left);
        qsort(nums,right, r);
    }
    public void swap(int i,int j,int[] nums){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
